﻿using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Text;

using ClipperLib;

namespace TreeLayoutPlayground
{
    using Polygon = List<IntPoint>;
    using Polygons = List<List<IntPoint>>;

    class CSGLayoutEngine : LayoutEngine
    {
        private static Polygon ShiftPolygon(Polygon poly, Size s)
        {
            return new Polygon(poly.Select(p => { return new IntPoint(p.X + s.Width, p.Y + s.Height); }));
        }

        private static Polygons ShiftPolygons(Polygons polys, Size s)
        {
            return new Polygons(polys.Select(p => { return ShiftPolygon(p, s); }));
        }

        public CSGLayoutEngine() { }

        private Polygon selfPolygon(Tree t)
        {
            // Get my own polygon with some padding
            return new Polygon {
                new IntPoint(t.MyBox.Left - HalfGap, t.MyBox.Top - HalfGap),
                new IntPoint(t.MyBox.Right + HalfGap, t.MyBox.Top - HalfGap),
                new IntPoint(t.MyBox.Right + HalfGap, t.MyBox.Bottom + HalfGap),
                new IntPoint(t.MyBox.Left - HalfGap, t.MyBox.Bottom + HalfGap)
            };
        }

        private Polygons getPolygons(Tree t, Size s)
        {
            // Get a polygonal representation of myself as a tree
            // This is the union of my polygon and the polygons of each
            // of my children
            Polygon sShifted = ShiftPolygon(selfPolygon(t), s);
            Clipper clipper = new Clipper();

            clipper.AddPolygon(sShifted, PolyType.ptSubject);
            foreach (Tree c in t.Children)
            {
                Polygons child = getPolygons(c, Size.Add(s, c.MyRelativeTranslation));
                clipper.AddPolygons(child, PolyType.ptSubject);
            }

            Polygons union = new Polygons();
            clipper.Execute(ClipType.ctUnion, union, PolyFillType.pftNonZero, PolyFillType.pftNonZero);

            return union;
        }

        public override void Layout(Tree tree)
        {
            tree.MyRelativeTranslation = Size.Empty;
            tree.MyBox.X = 0;
            tree.MyBox.Y = 0;

            if (tree.NumberOfChildren == 0)
            {
                tree.OverallSize = tree.MyBox.Size;
                return;
            }

            int top = tree.MyBox.Height + GapSize;
            Polygons placed = new Polygons();
            int sumX = 0;
            foreach (Tree c in tree.Children)
            {
                // Initial placement
                Layout(c);
                c.MyRelativeTranslation.Width = 0;
                c.MyRelativeTranslation.Height = top;

                Polygons child = getPolygons(c, c.MyRelativeTranslation);

                // Until I don't overlap anyone
                //   Find the largest overlapping area (x-axis only)
                //   Shift myself that far to the right
                int xshift;
                do
                {
                    //Polygons right = getPolygons(c, c.MyRelativeTranslation);
                    Clipper clip = new Clipper();
                    clip.AddPolygons(placed, PolyType.ptSubject);
                    clip.AddPolygons(child, PolyType.ptClip);

                    Polygons overlap = new Polygons();
                    clip.Execute(ClipType.ctIntersection, overlap, PolyFillType.pftNonZero, PolyFillType.pftNonZero);

                    xshift = 0;
                    foreach (Polygon poly in overlap)
                    {
                        int leftmost = int.MaxValue;
                        int rightmost = int.MinValue;
                        foreach (IntPoint p in poly)
                        {
                            leftmost = (int)Math.Min(p.X, leftmost);
                            rightmost = (int)Math.Max(p.X, rightmost);
                        }

                        xshift = Math.Max(rightmost - leftmost, xshift);
                    }

                    c.MyRelativeTranslation.Width += xshift;
                    child = ShiftPolygons(child, new Size(xshift, 0));
                } while (xshift > 0);

                // Add myself to the placed subtrees
                Clipper union = new Clipper();
                union.AddPolygons(placed, PolyType.ptSubject);
                union.AddPolygons(child, PolyType.ptSubject);
                union.Execute(ClipType.ctUnion, placed, PolyFillType.pftNonZero, PolyFillType.pftNonZero);

                // Used for placing myself centered above my children
                Point tc = c.GetTopCenter(c.MyRelativeTranslation);
                sumX += tc.X;
            }

            sumX /= tree.NumberOfChildren;
            int midX = sumX - (tree.MyBox.Width / 2);
            // Make sure I don't have anything going outside the bounds
            if (midX < 0)
            {
                foreach (Tree c in tree.Children)
                {
                    c.MyRelativeTranslation.Width += -midX;
                }

                midX = 0;
            }

            tree.MyBox.X = midX;

            // Use the Clipper to find the bounding box for me and my children
            Clipper clipper = new Clipper();
            clipper.AddPolygon(selfPolygon(tree), PolyType.ptSubject);
            clipper.AddPolygons(placed, PolyType.ptSubject);
            IntRect bound = clipper.GetBounds();

            tree.OverallSize = new Size(
                1 + (int)(bound.right - bound.left) - (2 * HalfGap),
                1 + (int)(bound.bottom - bound.top) - (2 * HalfGap));
        }
    }
}
